package slidingWindow;

import java.util.HashMap;

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 限制
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */

public class LongestSubstringWithoutRepeat_3 {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int len = 0;
        HashMap<Character, Integer> window = new HashMap<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);

            // 若一个字符的数量超过1，则说明当前窗口已经含有重复字符
            while (window.get(c) > 1) {
                // len = right - left -1，当c是一个重复字符时，right已经++了
                // 判断不能在此处，如果s全是不同字符，根本进不来循环
                //  if (len < right - left - 1) {
                //      System.out.println("left: " + left + " right: " + right);
                //      len = right - left - 1;
                //  }
                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                left++;
            }
            // 当每次循环结束，当前窗口中肯定都是不相同的字符
            len = Math.max(len, right - left);
        }
        return len;
    }
}
